1. Field of the Invention
The present invention relates in general to a switch for routing data between buses, and in particular to a switch having a non-blocking arbitration system.
2. Description of Related Art
Networks route data transmissions between network stations. In some network system buses typically connect network stations to a central hub or switch. A network hub is simply a repeater receiving a data transmission (e.g. an Ethernet data packet or an ATM cell) arriving on any one input bus and rebroadcasting outward on all output buses. A header in the data packet or cell indicates the packet or cell destination. Each network station looks at the header to determine if it should accept or ignore the data transmission. One disadvantage to a hub repeater is that each bus carrying data transmissions to a network station not only must convey transmissions directed to that station but must carry packets directed to all other stations as well. That can put a heavy load on all hub output buses at times of high traffic and can reduce network throughput.
A network switch, on the other hand, routes an incoming data transmission outward only on the bus leading to its destination, thereby reducing the traffic load on network buses. A network switch typically includes input buffers for receiving and storing incoming transmissions from the network stations, output buffers for storing and then transmitting outgoing transmissions to the network stations and an intelligent routing system for selectively providing a data routing path for each incoming data transmission from an input buffer to the appropriate output buffer. Each input buffer typically stores each incoming transmission, determines the destination output buffer from the routing data included in the packet or cell header, and then requests the routing system to provide a data path between the input buffer and the destination output buffer. When the routing system establishes the data path, the input buffer sends the transmission to the output buffer via the data path.
Since input buffers may have competing routing requests, the routing system must include an arbitration system for determining which requests are granted. Such an arbitration system for an Ethernet network switch is described in U.S. Pat. No. 5,689,664 entitled "Network Switch With Arbitration System", issued Nov. 18, 1997 to Chou et al, (incorporated herein by reference). When Chou's arbitration system grants a request it signals the input buffer that made the request that it may begin forwarding a data packet to the output buffer via the switching mechanism. When the arbitration system thereafter learns that the data packet has been sent to the output buffer and that the output buffer is ready to receive another data packet, the arbitration system allows all input buffers to once again compete for a data routing path to the output buffer.
In Chou's network switch, an input buffer stores all incoming data packets but requests a data routing path only to the output buffer that is to receive its longest-stored data packet. If that output buffer is busy, the requesting input buffer is not only blocked from forwarding its longest-stored data packet to the busy output buffer, it is also blocked from forwarding any later stored data packet to other output buffers, even when they are idle.
What is needed is a network switch having an improved arbitration system wherein an input buffer storing a data transmission destined for a busy output buffer is not blocked from sending a subsequently stored data transmission to an idle output buffer.